/**************************************************************
          File Name:Fibonacci.c
          Author: Abby Cin
          Mail: abbytsing@gmail.com
          Created Time: 2015-04-12 10:51:10
***************************************************************/

#include<stdio.h>
#include<stdlib.h>

typedef struct
{
    long m[4];
} Matrix;

Matrix tmp ={.m = {1,1,1,0}};

long recurencce(long n)
{
    if(n == 1 || n == 2)
        return 1;
    else
        return recurencce(n-1) + recurencce(n-2);
}

long loop(long n)
{
    long tmp1 = 1, tmp2 = 1, res, i;
    if(n == 1 || n ==2)
        return 1;
    else
        for(i = 3; i<= n; i++)
        {
            res = tmp1 + tmp2;
            tmp1 = tmp2;
            tmp2 = res;
        }
    return res;
}

Matrix matirx_multiply(const Matrix *m1, const Matrix *m2)
{
    Matrix res;
    res.m[0] = m1->m[0] * m2->m[0] + m1->m[1] * m2->m[2]; // F(n+1)
    res.m[1] = m1->m[0] * m2->m[1] + m1->m[1] * m2->m[3];
    res.m[2] = m1->m[2] * m2->m[0] + m1->m[3] * m2->m[2]; // F(n)
    res.m[3] = m1->m[2] * m2->m[1] + m1->m[3] * m2->m[3];
    return res;
}

Matrix matrix_power(long n)
{
    Matrix res;
    if(n == 1)
        res = tmp;
    else if(n % 2 == 0)
    {
        res = matrix_power(n / 2);
        res = matirx_multiply(&res, &res);
    } 
    else if(n % 2 == 1)
    {
        res = matrix_power((n-1)/2);
        res = matirx_multiply(&res, &res);
        res = matirx_multiply(&res, &tmp);
    }
    return res;
}

long _matrix(long n)
{
    Matrix res;
    if(n < 2)
        return 1;
    res = matrix_power(n - 1);
    return res.m[0]; // F(n+1)
}

int main(int argc,char *argv[])
{
    long size;
    long res;
    if(argc < 3)
    {
        fprintf(stderr, "%s method[1(recurse)|2(loop)|3(matrix)] size\n", argv[0]);
        exit(1);
    }
    
    size = atoi(argv[2]);

    switch(atoi(argv[1]))
    {
        case 1:
            res = recurencce(size);
            break;
        case 2:
            res = loop(size);
            break;
        case 3:
            res = _matrix(size);
            break;
    }
/*
    for(int i=1; i<= size; i++)
    {
        //res = recurencce(i);
        //res = loop(i);
        //res = _matrix(i);
        //printf("%ld\n", res);
    }
*/
    return 0;
}
